package leo.mystudy.leetcode;

/**
 * @author chao.li@quvideo.com
 * @date 2018/7/5 15:07
 */
public class IntegerBreak {
    //    给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
//
//    例如，给定 n = 2，返回1（2 = 1 + 1）；给定 n = 10，返回36（10 = 3 + 3 + 4）。
//
//    注意：你可以假设 n 不小于2且不大于58。
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        if (n == 4) {
            return 4;
        }
        // 若n-3<=3，停止递归，又因为4可以拆为2、2,4=2*2，所以若n-3为4，也可以停止递归。
        if (n - 3 <= 4) {
            return 3 * (n - 3);
        }
        return 3 * integerBreak(n - 3);
    }

    public static void main(String[] args) {
        System.out.println(new IntegerBreak().integerBreak(9));
    }


}
